import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int len = nums.length;

        //以i，j为结尾的等差子序列的个数, i  < j
        int[][] dp = new int[len][len];

        //key为nums的元素，value为key对应的下标
        HashMap<Long, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            List<Integer> list = map.getOrDefault((long)nums[i], new ArrayList<>());
            list.add(i);
            map.put((long)nums[i], list);
        }

        for (int i = 1; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                long a = (long)2 * nums[i] - nums[j];//可能会超int
                List<Integer> indexList = map.getOrDefault(a, new ArrayList<>());
                for (int index : indexList) {
                    if (index < i) {
                        dp[i][j] += (dp[index][i] + 1);
                    }
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                ret += dp[i][j];
            }
        }
        return ret;
    }
}
